#
# @lc app=leetcode.cn id=481 lang=python3
#
# [481] 神奇字符串
#

# @lc code=start
class Solution:
    def magicalString(self, n: int) -> int:
        if n < 4:
            return 1
        s = [0] * n
        s[:3] = [1, 2, 2]
        ans = 1
        i, j = 2, 3
        while j < n:
            size = s[i]
            num = 3 - s[j - 1]
            while size and j < n:
                if num == 1:
                    ans += 1
                s[j] = num
                j += 1
                size -= 1
            i += 1
        return ans
# @lc code=end
